The present invention relates to a polygon drawing method and a polygon drawing apparatus and, more particularly, to those for drawing a polygon which is colored inside its outline, by using data indicating the outline of the polygon.
When outputting characters to a printer or the like, the bit map font in which each character is represented as an array of dots has the advantage of rapidly displaying the characters on a screen and, therefore, this font has generally been used in computer systems and the like. In the bit map font, however, since the number of dots constituting each character is determined, the dots increase in size as the character is scaled up, and the stepwise notches called xe2x80x9cjaggyxe2x80x9d become conspicuous. As a result, the outline font has spread in recent years. In the outline font, each character is treated as a polygon and represented as the outline of the polygon. The outline font comprises coordinates of representative points specifying the polygon as the formula of the character, and data indicating curves or straight lines for connecting the representative points with each other. By using the outline font, even when a large character is printed, a beautiful print having no jaggy is obtained and, moreover, a character of an arbitrary size can be printed. The outline font has spread as being mounted on printers and word processors, and recently it is increasingly used for screen display of personal computers and the like.
When processing a character or the like by using the outline font, the procedure is as follows. The coordinates of plural points (representative points) specifying a polygon constituting a character are stored as data. When printing or displaying the character, the outline of the polygon constituting the character is calculated through the representative points, and the inside of the outline is painted. Accordingly, when printing characters of different sizes, it is possible to use a font which is scaled up or down by calculation based on the fundamental font. Therefore, the outline font is advantageous over the dot font like the bitmap font in that it doesn""t need to have different font data for different sizes of characters.
There are two typical methods for painting the inside of the outline, xe2x80x9cscan conversionxe2x80x9d and xe2x80x9cseed paintingxe2x80x9d. In the scan conversion method, with respect to the edges of a given polygon, intersections of each horizontal scanning line with the edges of the polygon are detected, and the space between the intersections is colored (refer to 3D computer graphics, written by Nakamae, published by Shoko-do, pp.117-120).
On the other hand, the seed painting method is as follows. Initially, one unit (one pixel) specified as the starting point (seed) of painting inside the outline is painted, and a pixel to be painted next is detected from pixels surrounding the seed pixel (starting point), and thereafter, the same process as above is repeated with the detected pixel as a new seed. The painting is completed when there are no more pixels to be a new seed (refer to Japanese Published Patent Applications Nos. Sho.62-83790 and Sho.62-192878).
Japanese Published Patent Applications Nos. Hei.1-296389 and Hei.3-116288 disclose improved methods based on the typical painting methods described above. In these methods, data indicating the outline of a character or the like (hereinafter referred to as outline data) is stored in a control plane, and the dots inside the outline are colored on the basis of the data.
To be specific, the method disclosed in Japanese Published Patent Application No. Hei.1-296389 is aimed at avoiding the difficulty in determining a starting point in the seed painting method, which difficulty will be described later. In this method, when storing the outline data in the control plane, a segment or a curve corresponding to the outline data is generated to be stored. Then, it is decided whether the generated segment (or curve) is positioned on the left side of the horizontal scanning line (in this case, the count value of the segment is odd) or on the right side of the scanning line (in this case, the count value of the segment is even), and control data indicating the result of this decision is generated, and painting is performed according to the control data while scanning in the horizontal direction, whereby the process of determining the starting point is dispensed with.
Further, the method disclosed in Japanese Published Patent Application No. Hei.3-116288 is aimed at reducing the processing load, as compared with the above-described painting methods. In this method, painting start data is subtracted from painting end data to obtain painting data which specifies painting. Thereby, the processing is simplified and the processing load is reduced.
Further, there is still another painting method disclosed in the specification of HD64412 by Hitachi. According to this method, painting data is generated by performing an EXOR (Exclusive OR) operation on a control plane from a reference line (left end) on the basis of outline data, and the dots inside the outline are colored on the basis of the painting data so generated, thereby simplifying the painting process.
By the way, also in the field of car navigation system which has been remarkably developed in recent years, high-quality characters can be displayed by using the outline font described above. Further, in the car navigation system, when displaying a graphic such as map information, buildings and natures (river, pond, etc.) are handled as polygons, and painting is performed on the basis of data indicating the outlines of the polygons in the same manner as described for the outline font, thereby displaying the map information according to various kinds of contraction scales. FIGS. 10(a)-10(d) are diagrams for explaining the polygon processing in the display of the car navigation system. FIG. 10(a) shows outline data for displaying a character xe2x80x9cAxe2x80x9d, and FIG. 10(b) shows the character obtained by painting the inside of the outline data. Like the character, the graphic shown in FIG. 10(d) is obtained on the basis of outline data of the graphic shown in FIG. 10(c).
In the conventional polygon drawing method so constructed, it is not necessary to prepare a font or a graphic pattern for each character size, and a character or a graphic with smooth outline can be displayed even when it is scaled up.
However, in the above-described scan conversion method, since the processing load due to sorting of coordinate data constituting the edges is considerable, the processing time is decided not by the size of the graphic but by the number of the edges. Therefore, when processing a character constituted by many edges, the processing takes time even if the character is a relatively small graphic. Further, since curves cannot be used in the outline, it is necessary to approximate straight lines to curves. So, in order to represent a high-quality character or the like, a lot of straight lines are needed, and the number of the edges increases significantly, resulting in an increase in processing time.
On the other hand, the problem of the seed painting method resides in the difficulty in determining a seed pixel to be a starting point. That is, in the seed painting algorithm, a graphic representing one character is handled as one polygon, and this is one continuous region. So, one graphic (character or the like) can be processed with one seed pixel determined. However, if the graphic (character or the like) has a constricted part, the continuous region is sometimes divided into plural regions when the graphic is scaled down. In the seed painting method, when there are plural regions each being surrounded by an outline, plural seed pixels must be specified. So, in order to avoid that a small region separated from one region remains unpainted, plural seed pixels must be specified. Accordingly, in this case, the character cannot be processed according to the relatively simple algorithm in which one seed pixel is selected for one character, and the procedure is complicated for appropriately processing the character.
As described above, Japanese Published Patent Application No. Hei.1-296389 has proposed a method which solves the above-described problems in the seed painting method. In this method, however, since segments or the like are generated while performing the above-described decision for generating control data and then the segments or the like are stored in the control plane, the processing load increases considerably due to the generation and storage of the segments or the like.
Further, the method disclosed in Japanese Published Patent Application No. Hei.30116288 has the following problems. FIGS. 11(a)-11(d) and 12(a)-12(b) are diagrams for explaining the processes and problems in this method.
FIG. 11(a) shows outline data for displaying a character xe2x80x9cAxe2x80x9d, and FIG. 11(b) shows the character to be obtained by painting the inside of the outline data. As described above, in this method, the outline data shown in FIG. 11(a) is scanned in the horizontal direction to generate odd data indicating the position where painting is started in the scanning line (painting start data) and even data indicating the position where the painting is ended (painting end data), and these data are arithmetically processed to obtain painting data indicating the region to be painted. In FIG. 11(a), the outline of the graphic to be drawn is shown by a line obtained by connecting adjacent ▪ with each other, and in FIG. 11(b), a region to be painted is shown by an array of ▪.
FIGS. 12(a) and 12(b) are diagrams for explaining the arithmetic processing in this method. FIG. 12(a) shows the processing performed on a scanning line 1101 shown in FIG. 11(c), and FIG. 12(b) shows the processing performed on a scanning line 1102 shown in FIG. 11(c). In FIG. 12(a), 1201 denotes a scanning line including 16 pixels, and this is identical to 1103 shown in FIG. 11(c). Further, 1202 denotes odd data indicating the painting start position in the scanning line 1101, 1203 denotes even data indicating the painting end position in the scanning line 1101, 1204 denotes painting data obtained by the arithmetic processing, and 1205 denotes the result of display corresponding to one horizontal scanning line, which is obtained according to the painting data 1204.
The odd data 1202 is 16-bit data, wherein only the bits corresponding to the pixels to be the painting start positions amongst the pixels included in the scanning line 1201 have the values xe2x80x9c1xe2x80x9d while the other bits have the value xe2x80x9c0xe2x80x9d. The even data 1203 is 16-bit data, wherein only the bits corresponding to the pixels to be the painting end positions amongst the pixels included in the scanning line 1201 have the values xe2x80x9c1xe2x80x9d while the other bits have the values xe2x80x9c0xe2x80x9d. The reason why each data is 16-bit data is because the resolution of the outline data is 16xc3x9716 (refer to FIG. 11(a)) and the number of pixels in the horizontal scanning line is 16.
As described above, according to this method, the painting data is obtained by subtracting the odd data (painting start data) from the even data (painting end data). As shown in FIG. 12(a), when processing the scanning line 1201, the painting data 1204 is obtained by subtracting the odd data 1202 from the even data 1203. The result of display for one horizontal scanning line obtained by painting the pixels corresponding to the bits of xe2x80x9c1xe2x80x9d in the painting data 1204, is shown by 1205. When 1205 is compared with 1201, the pixel at the left end of the region to be painted remains unpainted, i.e., a defect occurs, and the width of the font is narrowed at this portion.
FIG. 12(b) shows a similar process to the process shown in FIG. 12(a). Odd data 1207 and even data 1208 are obtained from a scanning line 1206 (identical to 1104 shown in FIG. 11(c)), and painting data 1209 is obtained by subtracting the odd data from the even data. The result of display corresponding to the painting data 1209 is shown by 1210. Also, in this case, when 1210 is compared with 1206, the pixel at the left end of the region to be painted remains unpainted, i.e., a defect occurs, and the width of the font is narrowed at this portion.
According to the above-described method, since the painting data is obtained by such simple subtraction, the processing load can be reduced. However, defects may occur in the data to be colored. That is, as shown in FIG. 11(d), the character xe2x80x9cAxe2x80x9d displayed according to the painting process of this method is thinner than the character xe2x80x9cAxe2x80x9d to be displayed originally (FIG. 11(b)). The countermeasure against this problem is to correct the painting data such that the outline including the unpainted portion is re-drawn, by using the outline data shown in FIG. 11(a). However, this re-drawing of the outline performed after generation of the painting data reduces the expected effect of reducing the processing load.
Meanwhile, the method disclosed in the specification of HD64412 aimed at reducing the processing load has the following problems. FIGS. 13(a)-13(f) are diagrams for explaining the processes and problems in this method. FIG. 13(a) shows outline data stored in a control plane, which is used in this method. FIG. 13(b) shows the result of display to be obtained according to the outline data shown in FIG. 13(a). Further, FIGS. 13(c)-13(f) are diagrams for explaining the procedures of this method.
In FIG. 13(c), 1301 denotes segment data which is a portion of the outline data shown in FIG. 13(a). In this method, left-to-right scanning is performed in the horizontal direction, and the inside of the outline is painted from the left in accordance with the segment data (outline data). In this process, with respect to a unit (pixels) for which xe2x80x9cpaintingxe2x80x9d has been done in the previous stage, xe2x80x9cpaintingxe2x80x9d is eliminated in the subsequent (present) stage. This is implemented by executing an EXOR operation.
To be specific, in procedure 1 shown in FIG. 13(c), painting based on the segment data 1301 is performed. Procedure 1 is started in the initial state where xe2x80x9cpaintingxe2x80x9d has not been performed. So, in procedure 1, a region 1302 (slashed region) is painted on the basis of the segment data 1301.
Procedure 1 is followed by procedure 2 shown in FIG. 13(d). Procedure 2 is performed on segment data 1303 included in the outline data shown in FIG. 13(a). Since procedure 2 is performed on the state obtained as the result of procedure 1, xe2x80x9cpaintingxe2x80x9d is eliminated by an EXOR operation from the region 1302 which has been painted as shown in FIG. 13(c). Accordingly, a region 1304 in FIG. 13(d) corresponding to the region 1302 in FIG. 13(c) is in the state where xe2x80x9cpaintingxe2x80x9d is not performed. Further, by executing the procedure 2, a region 1305 (slashed region) is painted according to segment data 1303. Likewise, in the following procedure 3 shown in FIG. 13(e), painting is performed according to segment data 1306, and in procedure 4 shown in FIG. 13(f), painting is performed according to segment data 1307, whereby the display result is obtained.
In this way, since painting is performed while executing the simple EXOR operation, the processing load is reduced. However, in the course of the above-described procedures, painting and the EXOR operation are repeatedly performed on the left-end portion of the graphic, i.e., this portion is once subjected to xe2x80x9cpaintingxe2x80x9d and the subjected to elimination of xe2x80x9cpaintingxe2x80x9d. Therefore, as seen from FIG. 13(f) in comparison with FIG. 13(b), a region to be painted remains unpainted. Although this problem can be solved by correcting the painting data with the outline data shown in FIG. 13(a) such that the whole outline including the unpainted portion is re-drawn, the re-drawing of the whole outline reduces the expected effect of reducing the processing load.
Further, the above-described painting process using outline data is restricted by the capacity of a storage unit. FIGS. 14(a) and 14(b) are diagrams for explaining this problem. FIG. 14(a) shows data indicating the outline of a river to be displayed in map information of a car navigation system, and FIG. 14(b) shows the displayed graphic of the river. The aforementioned process using outline data is based on the premise that it employs a storage unit having a capacity sufficient to store the outline data. Especially when handling plural polygons having different sizes as those displayed in the map information or the like, a storage unit having a sufficient capacity is needed, and this leads to an increase in device cost.
Further, the graphic (river) shown in FIG. 14(b) extends over a wide area, but the ratio of the region to be colored to the area is small, and moreover, the region to be colored is continuous. When such graphic (river) is processed by the conventional technique, since the conventional technique is for processing a region to be colored and a region to be uncolored equally and so it has not been used for processing a relatively wide and continuous region at one time, the processing efficiency is not high as a whole.
As described above, when displaying a polygon by using outline data indicating the outline of the polygon, it is difficult to realize both a reduction in processing load and a satisfactory display without defects of data. Further, since the processing is restricted by the capacity of the storage unit, the device cost increases to display various kinds of objects (polygons).
The present invention is made to solve the above-described problems and it is an object of the present invention to provide a polygon drawing method which can provide a satisfactory result of display without increasing the processing load.
It is another object of the present invention to provide a polygon drawing method which can display various kinds of objects by efficient processing without using a mass storage unit.
It is still another object of the present invention to provide a polygon drawing apparatus which can provide a satisfactory result of display without increasing the processing load.
It is a further object of the present invention to provide a polygon drawing apparatus which can display various kinds of objects by efficient processing without using a mass storage unit.
Other objects and advantages of the invention will become apparent from the detailed description that follows. The detailed description and specific embodiments described are provided only for illustration since various additions and modifications within the scope of the invention will be apparent to those of skill in the art from the detailed description.
According to a first aspect of the present invention, there is provided a polygon drawing method for drawing a polygon which is colored inside its outline, by using outline data indicating the outline of the polygon. This method comprises the steps of: performing, for a predetermined amount of the outline data, parallel exclusive-OR processes in units of amounts constituting the predetermined amount, thereby generating mask data which specifies xe2x80x9ccoloringxe2x80x9d for the inside of the outline; and drawing the polygon by using the generated mask data. Therefore, the processing load can be reduced by executing the relatively simple processes in parallel.
According to a second aspect of the present invention, in the polygon drawing method of the first aspect, the step of generating the mask data includes, besides the exclusive-OR processes, OR processes to obtain the OR of the predetermined amount of the outline data and each of the results of the parallel exclusive-OR processes performed on the predetermined amount of the outline data. Therefore, the processing load can be reduced by executing the relatively simple processes in parallel. Further, since the outline data can be immediately corrected in the process of generating the outline data, no defect of data occurs, resulting in satisfactory display. Moreover, an additional process for correcting the outline data can be dispensed with.
According to a third aspect of the present invention, there is provided a polygon drawing method for drawing a polygon which is colored inside its outline, by using outline data indicating the outline of the polygon. This method comprises the steps of: generating mask data specifying xe2x80x9ccoloringxe2x80x9d for the inside of the outline by using a predetermined amount of the outline data, and generating status data indicating whether or not the mask data generating status should be continued exceeding the predetermined amount of the outline data; drawing the polygon by using the generated mask data; and performing subsequent generation of mask data and status data, by using the status data obtained in the previous generation of mask data and status data, as well as the predetermined amount of the outline data. Therefore, the outline data can be divided into predetermined amounts to be processed efficiently and appropriately.
According to a fourth aspect of the present invention, in the polygon drawing method of the third aspect, the mask data is obtained by correcting mask data which has been generated by using the predetermined amount of the outline data indicating the outline, in accordance with the predetermined amount of the outline data. Therefore, the outline data can be divided into predetermined amounts to be processed efficiently and appropriately. Further, since the outline data can be immediately corrected in the process of generating the outline data, no defect of data occurs, resulting in satisfactory display. Moreover, an additional process for correcting the outline data can be dispensed with.
According to a fifth aspect of the present invention, there is provided a polygon drawing apparatus for drawing a polygon which is colored inside its outline, by using outline data indicating the outline of the polygon. This apparatus comprises outline data generation means for generating outline data indicating the outline of the polygon, on the basis of coordinate data indicating the coordinates of points constituting the polygon; mask data generation means for performing, for a predetermined amount of the outline data, parallel exclusive-OR processes in units of amounts constituting the predetermined amount, thereby generating mask data which specifies xe2x80x9ccoloringxe2x80x9d for the inside of the outline; and segment generation means for drawing the polygon by using the mask data generated by the mask data generation means. Therefore, the processing load can be reduced by executing the relatively simple processes.
According to a sixth aspect of the present invention, in the polygon drawing apparatus of the fifth aspect, the mask data generation means performs, besides the exclusive OR processes, OR processes to obtain the OR of the predetermined amount of the outline data and each of the results of the parallel exclusive-OR processes performed on the predetermined amount of the outline data. Therefore, the processing load can be reduced by executing the relatively simple processes in parallel. Further, since the outline data can be immediately corrected in the process of generating the outline data, no defect of data occurs, resulting in satisfactory display. Moreover, an additional process for correcting the outline data can be dispensed with.
According to a seventh aspect of the present invention, there is provided a polygon drawing apparatus for drawing a polygon which is colored inside its outline, by using outline data indicating the outline of the polygon. This apparatus comprises: outline data generation means for generating outline data indicating the outline of the polygon, on the basis of coordinate data indicating the coordinates of points constituting the polygon; mask data generation means for generating mask data specifying xe2x80x9ccoloringxe2x80x9d by using a predetermined amount of the outline data indicating the outline, and generating status data indicating whether or not the mask data generating status should be continued exceeding the predetermined amount of the outline data and, when the status data indicates xe2x80x9ccontinuationxe2x80x9d, continuing the mask data generation and the status data generation by using the predetermined amount of outline data generated in the next stage by the outline data generation means, and the status data indicating the previous processing status; and segment drawing means for drawing the polygon by using the mask data generated by mask data generation means. Therefore, the outline data can be divided into predetermined amounts to be processed efficiently and appropriately.
According to an eighth aspect of the present invention, in the polygon drawing apparatus of the seventh aspect, the mask data is obtained by correcting mask data which has been generated by the mask data generation means using the predetermined amount of the outline data indicating the outline, in accordance with the predetermined amount of the outline data. Therefore, the outline data can be divided into predetermined amounts to be processed efficiently and appropriately. Further, since the outline data can be immediately corrected in the process of generating the outline data, no defect of data occurs, resulting in satisfactory display. Moreover, an additional process for correcting the outline data can be dispensed with.
According to a ninth aspect of the present invention, the polygon drawing apparatus of the fifth or seventh aspect further comprises: storage means for temporarily storing the mask data generated by the mask data generation means; and the segment generation means performing drawing by using the mask data temporarily stored by the storage means. Therefore, the outline data can be divided into predetermined amounts to be processed efficiently and appropriately. Further, generation of mask data and drawing using the mask data can be executed in parallel, resulting in an increase in processing speed.